Collaborative applications, often referred to as groupware applications, permit two or more people, each using different computers, to share a common view of a virtual workspace and to manipulate a shared data object in that workspace. Typically, a copy of the collaborative application is executed at each user's computer to simulate the workspace and to manipulate a local copy of the data that is being collaboratively manipulated and displayed. For example, a collaborative drawing application may display the same drawing at each of a group of computers, and user's at each of those computers can change the drawing as well as view changes made by other users. One way in which this is done is to provide each user's computer with a local copy of the shared data object. The shared data object is then manipulated by the user's local copy of the collaborative application. The local copy of the shared data object is synchronized with copies of the shared data object that are maintained at other computers using synchronization messages exchanged between those computers. For example, in a shared word processing application, if a user at a first computer deletes a particular paragraph of a document, a message can be sent to other computers instructing copies of the collaborative application at those computers to delete the same paragraph from their local copy of the shared data object.
One problem facing a groupware application designer is to ensure that all copies of the shared data object are maintained in a consistent state. If proper controls are not in place, different manipulations of the shared data object may arise due to simultaneity conflicts and temporal errors. These errors, also referred to as ordering or sequencing errors, can occur when synchronization messages are received and/or processed in different orders at different computers.
A temporal error occurs when synchronization messages arrive at different computers in different orders. This can occur, e.g., due to different network delays between computers. As a result, different sequences of synchronization operations may be performed at different computers. Concurrency controls can address temporal errors by ensuring that operations at different computers are processed in a way that yields a consistent result. Broadly speaking, such concurrency control systems can be are characterized as being either “optimistic” or “pessimistic” (i.e., “non-optimistic”). Pessimistic systems, such as record locking and semaphores, can ensure that operations are both received and executed in their proper order. However, pessimistic systems may have a high delay in accessing the shared data object and this delay may impede the use of pessimistic controls in real-time collaborative systems.
Optimistic systems allow operations to be received and/or executed out-of-order. Optimist systems may have a relatively low delay compared to pessimistic systems, thus improving the real-time user experience. However, optimistic systems may need to employ complex error detection and repair to deal with out-of-order operations. One correction approach is to queue operations that arrive too early, or to undo out-of-order operations that have been executed, and then re-execute them in-order. Another approach is to use transformations to modify received out-of-order operations into a new set of operations. In the transformation approach, transformations can be applied to operations so that different execution sequences produce the same result. FIG. 1 shows two message processing sequences (shown, respectively, as the left and right side of FIG. 1). The left side sequence shows operation α followed by β′ (a transformation of the operation β) being performed at a computer 101. This sequence has the same effect as the sequence shown on the right-side of FIG. 1 in which the operation β is followed by α′ (a transformation of the operation α) at computer 102. The operation transformation method illustrated by FIG. 1 requires a transformation matrix that, for many applications, can be difficult or impossible to determine.
Although solutions exist to handle some data consistency problems, software development can be improved by additional concurrency systems to address particular design needs of software developers.